package com.gitee.wsl.lang.bits

import com.gitee.wsl.ext.base.Arrays.arraycopy
import com.gitee.wsl.ext.base.Arrays.fill
import com.gitee.wsl.ext.base.SIZE
import com.gitee.wsl.ext.bitcode.bitCount
import com.gitee.wsl.ext.bitcode.numberOfLeadingZeros
import com.gitee.wsl.ext.bitcode.numberOfTrailingZeros
import kotlin.math.min


/**
 * Bare metal bit set implementation. For performance reasons, this implementation does not check for index bounds nor
 * expand the bit set size if the specified index is greater than the size.
 */
class FixedBitSet(data: LongArray)  {
    val data: LongArray

    constructor(bits: Int) : this(LongArray((bits + 63) / 64))

    /**
     * Sets the bit at specified index.
     *
     * @param index - position
     */
    fun set(index: Int) {
        this.data[index ushr 6] = this.data[index ushr 6] or (1L shl index)
    }

    /**
     * Returns true if the bit is set in the specified index.
     *
     * @param index - position
     * @return - value at the bit position
     */
    fun get(index: Int): Boolean {
        return (this.data[index ushr 6] and (1L shl index)) != 0L
    }
    
    
    /**
     * Number of bits
     */
    fun size(): Int {
        return data.size * Long.SIZE
    }

    val dataLength: Int
        get() = data.size

    /**
     * Clear the bit set.
     */
    fun clear() {
        fill(this.data, 0)
    }

      fun set(fromIndex: Int, toIndex: Int) {
        if (fromIndex == toIndex) return

        val startWordIndex = wordIndex(fromIndex)
        val endWordIndex = wordIndex(toIndex - 1)

        val firstWordMask = WORD_MASK shl fromIndex
        val lastWordMask = WORD_MASK ushr -toIndex
        if (startWordIndex == endWordIndex) {
            this.data[startWordIndex] = this.data[startWordIndex] or (firstWordMask and lastWordMask)
        } else {
            this.data[startWordIndex] = this.data[startWordIndex] or firstWordMask

            for (i in startWordIndex + 1..<endWordIndex) this.data[i] = WORD_MASK

            this.data[endWordIndex] = this.data[endWordIndex] or lastWordMask
        }
    }

      fun count(fromIndex: Int, toIndex: Int): Int {
        var cnt = 0
        var i = toIndex
        while ((previousSetBit(i - 1).also { i = it }) >= fromIndex) {
            cnt++
        }
        return cnt
    }

      fun clear(bitIndex: Int) {
        val wordIndex = wordIndex(bitIndex)
        this.data[wordIndex] = this.data[wordIndex] and (1L shl bitIndex).inv()
    }

      fun clear(fromIndex: Int, toIndex: Int) {
        if (fromIndex == toIndex) return

        val startWordIndex = wordIndex(fromIndex)
        val endWordIndex = wordIndex(toIndex - 1)

        val firstWordMask = WORD_MASK shl fromIndex
        val lastWordMask = WORD_MASK ushr -toIndex
        if (startWordIndex == endWordIndex) {
            this.data[startWordIndex] = this.data[startWordIndex] and (firstWordMask and lastWordMask).inv()
        } else {
            this.data[startWordIndex] = this.data[startWordIndex] and firstWordMask.inv()

            for (i in startWordIndex + 1..<endWordIndex) this.data[i] = 0

            this.data[endWordIndex] = this.data[endWordIndex] and lastWordMask.inv()
        }
    }

      fun cardinality(): Int {
        var sum = 0
        var i = 0
        val n = data.size
        while (i < n) {
            sum += this.data[i].bitCount()
            i++
        }
        return sum
    }

    val isEmpty: Boolean
        get() {
            var i = 0
            val n = data.size
            while (i < n) {
                if (this.data[i] != 0L) return false
                i++
            }
            return true
        }

      fun flip(bitIndex: Int) {
        val wordIndex = wordIndex(bitIndex)
        this.data[wordIndex] = this.data[wordIndex] xor (1L shl bitIndex)
    }

      fun flip(fromIndex: Int, toIndex: Int) {
        if (fromIndex == toIndex) return

        val startWordIndex = wordIndex(fromIndex)
        val endWordIndex = wordIndex(toIndex - 1)

        val firstWordMask = WORD_MASK shl fromIndex
        val lastWordMask = WORD_MASK ushr -toIndex
        if (startWordIndex == endWordIndex) {
            this.data[startWordIndex] = this.data[startWordIndex] xor (firstWordMask and lastWordMask)
        } else {
            this.data[startWordIndex] = this.data[startWordIndex] xor firstWordMask

            for (i in startWordIndex + 1..<endWordIndex) this.data[i] = this.data[i] xor WORD_MASK

            this.data[endWordIndex] = this.data[endWordIndex] xor lastWordMask
        }
    }

      fun and(bs: FixedBitSet) {
        if (this === bs) return

        val set = toBitSet(bs)
        var wordsInUse = this.dataLength

        while (wordsInUse > set.dataLength) this.data[--wordsInUse] = 0

        for (i in 0..<wordsInUse) this.data[i] = this.data[i] and set.data[i]
    }

      fun andNot(bs: FixedBitSet) {
        val set = toBitSet(bs)

        val wordsInUse = this.dataLength
        for (i in min(wordsInUse, set.dataLength) - 1 downTo 0) this.data[i] = this.data[i] and set.data[i].inv()
    }

      fun or(bs: FixedBitSet) {
        if (this === bs) return

        val set = toBitSet(bs)
        val wordsInUse = this.dataLength
        val wordsInCommon = min(wordsInUse, set.dataLength)

        require(wordsInUse >= set.dataLength){ "data length is too large"}

        for (i in 0..<wordsInCommon) this.data[i] = this.data[i] or set.data[i]

        if (wordsInCommon < set.dataLength)
            arraycopy(set.data, wordsInCommon,
            this.data, wordsInCommon, set.dataLength - wordsInCommon)
    }

      fun xor(bs: FixedBitSet) {
        val set = toBitSet(bs)
        val wordsInUse = this.dataLength
        val wordsInCommon = min(wordsInUse, set.dataLength)

        require(wordsInUse >= set.dataLength){"data length is too large"}

        for (i in 0..<wordsInCommon) this.data[i] = this.data[i] xor set.data[i]

        if (wordsInCommon < set.dataLength)
            arraycopy(
            set.data, wordsInCommon,
            this.data, wordsInCommon, set.dataLength - wordsInCommon
        )
    }

    fun toBitSet(bs: FixedBitSet): FixedBitSet {
        return bs as FixedBitSet
    }

      fun intersects(bs: FixedBitSet): Boolean {
        val set = toBitSet(bs)

        for (i in min(data.size, set.dataLength) - 1 downTo 0) if ((this.data[i] and set.data[i]) != 0L) return true
        return false
    }

    /**
     * Deserialize long array as bit set.
     *
     * @param data - bit array
     */
    init {
        require(data.isNotEmpty()) { "data length is zero!" }
        this.data = data
    }

    fun previousSetBit(fromIndex: Int): Int {
        if (fromIndex < 0) {
            return -1
        }

        var u = wordIndex(fromIndex)

        var word = this.data[u] and (WORD_MASK ushr -(fromIndex + 1))

        while (true) {
            if (word != 0L) return (u + 1) * BITS_PER_WORD - 1 - Long.numberOfLeadingZeros(word)
            if (u-- == 0) return -1
            word = this.data[u]
        }
    }

      fun nextSetBit(fromIndex: Int): Int {
        // Guard.assertTrue(fromIndex >= 0, "collection.err_fromIndex_must_not_negative");

        var u = wordIndex(fromIndex)
        val wordsInUse = data.size
        if (u >= wordsInUse) return -1

        var word = this.data[u] and (WORD_MASK shl fromIndex)

        while (true) {
            if (word != 0L) return (u * BITS_PER_WORD) + Long.numberOfTrailingZeros(word)
            if (++u == wordsInUse) return -1
            word = this.data[u]
        }
    }

      fun nextClearBit(fromIndex: Int): Int {
        // Guard.assertTrue(fromIndex >= 0, "collection.err_fromIndex_must_not_negative");

        val wordsInUse = data.size
        var u = wordIndex(fromIndex)
        if (u >= wordsInUse) return fromIndex

        var word = this.data[u].inv() and (WORD_MASK shl fromIndex)

        while (true) {
            if (word != 0L) return (u * BITS_PER_WORD) + Long.numberOfTrailingZeros(word)
            if (++u == wordsInUse) return wordsInUse * BITS_PER_WORD
            word = this.data[u].inv()
        }
    }

      fun cloneInstance(): FixedBitSet {
        return FixedBitSet(data.clone())
    }

    companion object {
        private const val ADDRESS_BITS_PER_WORD = 6
        private val BITS_PER_WORD = 1 shl ADDRESS_BITS_PER_WORD

        //  private final static int BIT_INDEX_MASK = BITS_PER_WORD - 1;
        private const val WORD_MASK = -0x1L

        private fun wordIndex(bitIndex: Int): Int {
            return bitIndex shr ADDRESS_BITS_PER_WORD
        }
    }
}